#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <limits>

using namespace std;

class Compact_segment_tree
{
private:
	struct Tree_node
	{
		Tree_node(Tree_node *left, Tree_node *right, int l, int r, int v, bool leaf) :
			left(left), right(right), l(l), r(r), v(v), leaf(leaf) {}

		Tree_node *left, *right;
		int l, r, v;
		bool leaf;
	};

public:
	Compact_segment_tree(int l, int r, int v)
	{
		root = new Tree_node(nullptr, nullptr, l, r, v, true);
	}

	void set_range(int l, int r, int v)
	{
		vector<Tree_node*> decomposition;
		decompose(root, l, r, decomposition);
		for (auto it = decomposition.begin(); it != decomposition.end(); ++it)
		{
			(*it)->v = v;
			if (!(*it)->leaf)
				collapse(*it);
		}
	}

	int get(int i)
	{
		Tree_node *cur_node = root;
		while (cur_node->leaf != true)
		{
			if (i > (cur_node->l+cur_node->r)/2)
				cur_node = cur_node->right;
			else
				cur_node = cur_node->left;
		}
		return cur_node->v;
	}

	void print()
	{
		cout << endl << "Compact segment tree:" << endl;
		print_rec(root);
	}

private:
	Tree_node *root;

	void print_rec(Tree_node *node)
	{
		if (node->leaf)
		{
			cout << "[" << node->l << ", " << node->r << "]" << " -> " << node->v << endl;
			return;
		}

		print_rec(node->left);
		print_rec(node->right);
	}

	void decompose(Tree_node *node, int l, int r, vector<Tree_node*> &res)
	{
		if (l > r || node->r < l ||  node->l > r)
			return;

		if (node->l == l && node->r == r)
		{
			res.push_back(node);
			return;
		}

		int med = (node->l+node->r)/2;
		if (node->leaf)	// expand
		{
			node->leaf = false;
			node->left = new Tree_node(nullptr, nullptr, node->l, med, node->v, true);
			node->right = new Tree_node(nullptr, nullptr, med+1, node->r, node->v, true);
		}

		decompose(node->left, l, med<r?med:r, res);
		decompose(node->right, med+1>l?med+1:l, r, res);
	}

	void collapse(Tree_node *node)
	{
		if (node->leaf)
		{
			return;
		}

		collapse(node->left);
		delete node->left;
		node->left = nullptr;

		collapse(node->right);
		delete node->right;
		node->right = nullptr;

		node->leaf = true;
	}
};

template<class T>
class RBtree
{
private:
	enum Color
	{
		RED,
		BLACK
	};

	struct Node
	{
		Node(Node *parent, Node *left, Node *right, T v, Color c) :
			parent(parent), left(left), right(right), v(v), c(c) {}

		Node *parent, *left, *right;
		T v;
		Color c;
	};

public:
	RBtree() : //sentinel_leaf(new Node(nullptr, nullptr, nullptr, T(), BLACK)),
		root(nullptr)
	{ }

	T* search(const T &elem)
	{
		return search_rec(root, elem);
	}

	void insert(const T &elem)
	{
		Node* node = insert_rec(root, nullptr, elem);

		// re-balance tree after insertion (different cases)
		insert_case_1(node);
	}

private:
	Node *root;
	//const Node *sentinel_leaf;

	bool is_root(const Node *node)
	{
		return node->parent == nullptr;
	}

	bool is_leaf(const Node *node)
	{
		return node->left == nullptr && node->right == nullptr;
	}

	Node* grandparent(Node *node)
	{
		if (node == nullptr || node->parent == nullptr)
			return nullptr;
		return node->parent->parent;
	}

	Node* uncle(Node *node)
	{
		Node* gp = grandparent(node);
		if (gp == nullptr)
			return nullptr;

		if (node->parent == gp->left)
			return gp->right;
		else
			return gp->left;
	}

	void insert_case_1(Node *node)
	{
		if (is_root(node))
			node->c = BLACK;
		else
			insert_case_2(node);
	}

	void insert_case_2(Node *node)
	{
		if (node->parent->c == BLACK)
			return;
		else 
			insert_case_3(node);
	}

	void insert_case_3(Node *node)
	{
		Node *u = uncle(node);
		if (u != nullptr && u->c == RED)
		{
			node->parent->c = BLACK;
			u->c = BLACK;
			grandparent(node)->c = RED;
			insert_case_1(grandparent(node));
		}
		else
		{
			insert_case_4(node);
		}
	}

	void insert_case_4(Node *node)
	{
		Node *g = grandparent(node);

		if (node == node->parent->right && node->parent == g->left)
		{
			rotate_left(node->parent);
			node = node->left;
		}
		else if (node == node->parent->left && node->parent == g->right)
		{
			rotate_right(node->parent);
			node = node->right;
		}

		insert_case_5(node);
	}

	void insert_case_5(Node *node)
	{
		Node *gp = grandparent(node);

		node->parent->c = BLACK;
		gp->c = RED;
		if (node == node->parent->left)
			rotate_right(node);
		else
			rotate_left(node);
	}

	void rotate_left(Node *node)
	{
		Node *p = node->parent;
		p->right = node->left;
		node->left = p;

		node->parent = p->parent;
		p->parent = node;
	}

	void rotate_right(Node *node)
	{
		Node *p = node->parent;
		p->left = node->right;
		node->right = p;

		node->parent = p->parent;
		p->parent = node;
	}

	Node* insert_rec(Node *cur_node, Node *parent, const T &elem)
	{
		// reached leaf
		if (cur_node == nullptr)
		{
			Node *inserted = new Node(parent, nullptr, nullptr, elem, RED);

			if (parent != nullptr)
			{
				if (parent->v > elem)
					parent->right = inserted;
				else
					parent->left = inserted;
			}

			return inserted;
		}

		if (cur_node->v > elem)
		{
			return insert_rec(cur_node->right, cur_node, elem);
		}
		else
		{
			return insert_rec(cur_node->left, cur_node, elem);
		}
	}

	T* search_rec(const Node *node, const T &elem)
	{
		if (node == nullptr)
			return nullptr;

		if (node->v == elem)
			return &node->v;

		if (node->v > elem)
			search_rec(root->right, elem);
		else
			search_rec(root->left, elem);
	}
};

void test_cst()
{
	Compact_segment_tree cst(0, 1e6, 0);
	cst.set_range(0,2,1);
	cst.print();

	cst.set_range(0,1,1);
	cst.print();

	cst.set_range(0,5,0);
	cst.print();

	cst.set_range(8,10,1);
	cst.print();

	cst.set_range(1,2,1);
	cst.print();

	cout << cst.get(2) << endl;
	cout << cst.get(8) << endl;

	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();
}

void main()
{
	//test_cst();
	RBtree<int> rbt;
	rbt.insert(1);
}